# 子集II: https://leetcode-cn.com/problems/subsets-ii/submissions/

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        """
            只是比子集，增加了一个去重的逻辑
        """
        rst = []
        nums.sort()
        def getSubSets(arr, idx):
            rst.append(arr[:])
            for i in range(idx, len(nums)):
                # 去重
                if i > idx and nums[i] == nums[i-1]:
                    continue
                arr.append(nums[i])
                getSubSets(arr, i + 1)
                arr.pop()

        getSubSets([], 0)
        return rst